package cn.walls1717.dataStructure.sort;

import cn.walls1717.leetcode.util.AlgorithmUtil;

import java.util.Arrays;

/**
 * 快速排序
 *
 * @author walls1717
 * @since 2022-04-29
 **/
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {3, 1, 5, 2, 4};
        quickLomuto(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    private static void quickLomuto(int[] arr, int l, int h) {
        if (l >= h) {
            return;
        }
        int p = partitionLomuto(arr, l, h);
        quickLomuto(arr, p + 1, h);
        quickLomuto(arr, l, p - 1);
    }

    /**
     * 罗穆托单边快排
     * @param arr 待排序数组
     * @param l 0
     * @param h 数组最大下标
     * @return 划分
     */
    private static int partitionLomuto(int[] arr, int l, int h) {
        // 基准点
        // 单边快排基准点设置在数组最后一个元素
        int pv = arr[h];
        int i = l;
        // j循环数组，发现比基准点小的元素，与i交换位置，之后i再后移
        // 要是j走遍整个数组，都没发现比基准点小的元素
        // 那么证明基准点左边的元素都比基准点小
        for (int j = l; j < h; ++j) {
            if (arr[j] < pv) {
                // 如果i和j仍在同一个位置，那么不进行交换，减少交换次数
                if (i != j) {
                    AlgorithmUtil.swap(arr, i, j);
                }
                ++i;
            }
        }
        // 如果i已经走到了基准点位置，那么就不用再与基准点交换位置了
        if (i != h) {
            // 基准点与i交换位置，达到基准点左边的元素比基准点小，右边比基准点大
            AlgorithmUtil.swap(arr, i, h);
        }
        return i;
    }
}
